#include <iostream>
#include <vector>
using namespace std;

struct FunctionResults{
    int temp_low;
    int temp_high;
    int temp_sum;
};

FunctionResults find_max_corssing_subarray(vector<int>& arr, int low, int mid, int high)
{
    int left_sum = -10000;
    int temp_sum = 0;
    int max_left = mid;
    int max_right = 0;
    for(int i=mid;i>=low;i=i-1)
    {
        temp_sum = temp_sum + arr[i];
        if (temp_sum > left_sum)
        {
            left_sum = temp_sum;
            max_left = i;
        }
    }

    int right_sum = -10000;
    temp_sum = 0;
    for (int j=mid+1;j<=high;j=j+1)
    {
        temp_sum = temp_sum + arr[j];
        if (temp_sum > right_sum)
        {
            right_sum = temp_sum;
            max_right = j;
        }
    }
    FunctionResults res;
    res.temp_low = max_left;
    res.temp_high = max_right;
    res.temp_sum = left_sum + right_sum;
    return res;
}

FunctionResults find_max_subarray(vector<int>& arr, int low, int high)
{
    FunctionResults final_res;
    int left_low, left_high, left_sum;
    int right_low, right_high, right_sum;
    int cross_low, cross_high, cross_sum;
    FunctionResults left, right, cross;

    if (high ==low)
    {
        final_res.temp_low = low;
        final_res.temp_high = high;
        final_res.temp_sum = arr[low];
        return final_res;
    }
    else
    {
        int mid = (low+high)/2;
        left = find_max_subarray(arr,low,mid);
        right = find_max_subarray(arr,mid+1,high);
        cross = find_max_corssing_subarray(arr,low,mid,high);
        if (left.temp_sum  >= right.temp_sum && left.temp_sum >= cross.temp_sum)
        {
            return left;
        }
        else if (right.temp_sum  >= left.temp_sum && right.temp_sum >= cross.temp_sum)
        {
            return right;
        }
        else
        {
            return cross;
        }

    }
}



int main(){
    vector<int> example = {-2, 0, -1, 0, 2, -3, 1, 2};
    FunctionResults res = find_max_subarray(example, 0,example.size() -1);
    cout << res.temp_low << endl;
    cout << res.temp_high << endl;
    cout << res.temp_sum << endl;
    cout << example.size() <<endl;
}